import pulp Saint‑Exupéry ruler
In [1]:
In [2]:
ruler = [i for i in range(21)]In [3]:
# create problem
prob = pulp.LpProblem("ruler", pulp.LpMinimize)
# x[i]=1 <=> mark on unit i
x = pulp.LpVariable.dicts("x",ruler,cat=pulp.LpBinary)
# y[i][j]=1 <=> mark on units i and j
y = pulp.LpVariable.dicts("y",(ruler,ruler),cat=pulp.LpBinary)
# minimize number of marks
prob+= pulp.lpSum(x)
for i in ruler:
for j in ruler:
if j>i:
prob+= y[i][j]<= x[i]
prob+= y[i][j]<= x[j]
prob+= x[i]+x[j] <= y[i][j]+1
for k in ruler:
if k>0:
prob+= pulp.lpSum(y[i][j] for i in ruler for j in ruler if j>i if j-i==k)>=1, "length_%s"%k
# match initial conditions
prob+= x[1]==1
prob+= x[4]==1
prob+= x[6]==1In [4]:
prob.solve()1
In [5]:
print("mark")
print("----")
for i in ruler:
if pulp.value(x[i])>0.9:
print(i)mark
----
0
1
4
6
11
18
19
20
In [6]:
print("length -> endpoints")
print("-------------------")
for k in ruler:
if k>0:
for i in ruler:
for j in ruler:
if j>i and j-i==k:
if pulp.value(y[i][j])>0.9:
print(k,"->",j,i)length -> endpoints
-------------------
1 -> 1 0
1 -> 19 18
1 -> 20 19
2 -> 6 4
2 -> 20 18
3 -> 4 1
4 -> 4 0
5 -> 6 1
5 -> 11 6
6 -> 6 0
7 -> 11 4
7 -> 18 11
8 -> 19 11
9 -> 20 11
10 -> 11 1
11 -> 11 0
12 -> 18 6
13 -> 19 6
14 -> 18 4
14 -> 20 6
15 -> 19 4
16 -> 20 4
17 -> 18 1
18 -> 18 0
18 -> 19 1
19 -> 19 0
19 -> 20 1
20 -> 20 0
In [7]:
import plotly.express as px
import pandas as pd
def make_ruler(
start=0, end=10, ticks=None,
ruler_height=1.0, tick_height=0.7,
label_offset=-0.15, label_size=36,
bg_color="#e6e6e6", border_color="black",
border_thickness=6, tick_width=6,
width_px=1000, height_px=220
):
if ticks is None:
ticks = list(range(int(start), int(end)+1))
base = pd.DataFrame({"x": [], "y": []})
fig = px.scatter(base, x="x", y="y")
# Body
fig.add_shape(
type="rect",
x0=start, x1=end,
y0=0, y1=ruler_height,
fillcolor=bg_color,
line=dict(color=border_color, width=border_thickness),
layer="below"
)
# Ticks + labels
for x in ticks:
fig.add_shape(
type="line",
x0=x, x1=x,
y0=ruler_height, y1=ruler_height - tick_height,
line=dict(color=border_color, width=tick_width)
)
fig.add_annotation(
x=x, y=label_offset,
text=str(x),
showarrow=False,
font=dict(size=label_size, color=border_color),
align="center",
yanchor="top"
)
pad = max((end - start) * 0.02, 0.2)
fig.update_layout(
width=width_px, height=height_px,
margin=dict(l=20, r=20, t=10, b=10),
plot_bgcolor="white",
)
fig.update_xaxes(range=[start - pad, end + pad],
showgrid=False, showticklabels=False,
visible=False, fixedrange=True)
fig.update_yaxes(range=[label_offset - 0.8, ruler_height + 0.3],
showgrid=False, showticklabels=False,
visible=False, fixedrange=True)
return fig
# Example
fig = make_ruler(start=0, end=ruler[-1], ticks=[i for i in ruler if pulp.value(x[i])>0.9])
fig.show()